package main

import (
	"fmt"
	"sort"
)

func main() {
	num1 := []int{1, 2, 3, 0, 0, 0}
	num2 := []int{2, 5, 6}
	m := 3
	n := 3
	merge3(num1, m, num2, n)
	fmt.Printf("%v\n", num1)
}

// 合并数组后再排序
func merge(nums1 []int, m int, nums2 []int, n int) {
	for i := 0; i < n; i++ {
		nums1[m+i] = nums2[i]
	}

	sort.Ints(nums1)
}

// 双指针
func merge2(nums1 []int, m int, nums2 []int, n int) {
	p1 := 0
	p2 := 0
	sorted := make([]int, 0, m+n)
	for p1 < m || p2 < n {
		if p1 == m {
			sorted = append(sorted, nums2[p2:]...)
			break
		} else if p2 == n {
			sorted = append(sorted, nums1[p1:]...)
			break
		} else if nums1[p1] < nums2[p2] {
			sorted = append(sorted, nums1[p1])
			p1++
		} else {
			sorted = append(sorted, nums2[p2])
			p2++
		}
	}
	copy(nums1, sorted)
}

// 逆向双指针
func merge3(nums1 []int, m int, nums2 []int, n int) {
	p1 := m - 1
	p2 := n - 1
	length := m + n - 1
	for p1 >= 0 || p2 >= 0 {
		if p1 == -1 {
			nums1[length] = nums2[p2]
			p2--
			length--
		} else if p2 == -1 {
			nums1[length] = nums1[p1]
			p1--
			length--
		} else if nums1[p1] > nums2[p2] {
			nums1[length] = nums1[p1]
			p1--
			length--
		} else {
			nums1[length] = nums2[p2]
			p2--
			length--
		}
	}
}
